package com.kavinz.algo.queue;

import com.kavinz.algo.stack.LinkedListStack;

/**
 * <Cracking the coding interview><br>
 * Exercise 3.5<br>
 * Implement a MyQueue class which implements a queue using two stacks
 * 
 * @author Kevin Zhao
 * 
 */
public class MyQueue<E> {

	LinkedListStack<E> reverseOrderStack = new LinkedListStack<E>();
	LinkedListStack<E> normalOrderStack = new LinkedListStack<E>();

	public void enqueue(E element) {
		reverseOrderStack.push(element);
	}

	public E dequeue() {
		// lazy 
		if(!normalOrderStack.isEmpty())
			return normalOrderStack.pop();
		// use the normalOrderStack to reverse the order of elements
		while (!reverseOrderStack.isEmpty())
			normalOrderStack.push(reverseOrderStack.pop());
		return normalOrderStack.pop();
	}
	public int size()
	{
		return reverseOrderStack.size()+normalOrderStack.size();
	}

public static void main(String[] args) { 
		
		MyQueue<String> queue = new MyQueue<String>();
		
		queue.enqueue("a");
		queue.enqueue("b");
		queue.enqueue("c");
		
		System.out.println("dequeue:"+queue.dequeue()+";size:"+queue.size());
		System.out.println("dequeue:"+queue.dequeue()+";size:"+queue.size());
		System.out.println("dequeue:"+queue.dequeue()+";size:"+queue.size());
	
		queue.enqueue("d");
		queue.enqueue("e");
		
		System.out.println("dequeue:"+queue.dequeue()+";size:"+queue.size());
}
}
